class Solution:
  def cuttingRope(self, n: int) -> int:
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
      tmp_max = 0
      for j in range(1, i):
        tmp = max(dp[j], j) * max(dp[i-j], i-j)
        # print('j={}, tmp={}'.format(str(j), str(tmp)))
        if tmp > tmp_max:
          tmp_max = tmp
      dp[i] = tmp_max
    # print('dp', dp[1:])
    return dp[-1]


'''
STATUS: LEARNT
TRIES:  N/A
TIME:   52 MS
MEMORY: 13.7 MB
'''
if __name__ == "__main__":
  solution = Solution()
  print(solution.cuttingRope(7))